package com.my.study.structures.sort;

import java.util.Arrays;

/**
 * @author Carlos
 * @version 1.0
 * @Description 归并排序
 * <p>
 * 先分，后治：分到只有一个元素，再一步步合并
 * <p>
 * 可以使用递归，也可以使用迭代
 * <p>
 * 难点在于治，即合并有序数组的阶段
 * @date 2021/7/22 22:55
 **/
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        int[] temp = new int[arr.length];

        sort(arr, 0, arr.length - 1, temp);

        System.out.println(Arrays.toString(arr));

    }

    private static void sort(int[] arr, int left, int right, int[] temp) {
//        for (int i = left; i <= right; i++) {
//            System.out.print(arr[i] + "\t");
//        }
//        System.out.println("");

        if (left < right) {
            int mid = (left + right) / 2;

            // 左递归
            sort(arr, left, mid, temp);

            // 右递归
            sort(arr, mid + 1, right, temp);

            // 合并
            merge(arr, left, mid, right, temp);
        }

    }


    /**
     * 数组合并
     *
     * @param arr   待排序的数组
     * @param left  左边有序序列的初始索引
     * @param mid   中间索引
     * @param right arr数组的长度，即数组最右边索引
     * @param temp
     */
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        // 左边有序序列的初始索引
        int i = left;
        // 右边有序序列的初始索引
        int j = mid + 1;
        // 临时temp的初始索引
        int t = 0;

        // 先把左右两边（有序）的数据按照规则填充到temp数组中，
        // 直到有一边处理完毕
        while (i <= mid && j <= right) {
            // 左 <= 右，既把左边的当前数据拷贝到temp中
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
//                t += 1;
//                i += 1;
            }
            // 左 > 右，既把右边的当前数据copy到temp中
            else {
                temp[t++] = arr[j++];
//                t += 1;
//                j += 1;
            }
        }


        // 把剩余的一边继续填充到temp中
        // 左边序列还有剩余，则把剩余的数据全部填充到temp
        while (i <= mid) {
            temp[t++] = arr[i++];
//            t += 1;
//            i += 1;
        }
        // 反之
        while (j <= right) {
            temp[t++] = arr[j++];
//            t += 1;
//            j += 1;
        }


        // 最后，把temp的数据copy到arr中
        // 注意，并不是每次拷贝所有
        t = 0;
        int tempLeft = left;
        // 第一次合并：tempLeft = 0, right = 1
        // 第二次合并：tempLeft = 2, right = 3
        // 第三次合并：tempLeft = 0, right = 3
        // ... 最后一次(第七次) tempLeft = 0, right = 7
        System.out.println("tempLeft=" + tempLeft + " right=" + right);
        while (tempLeft <= right) {
            arr[tempLeft++] = temp[t++];
//            tempLeft += 1;
//            t += 1;
        }

    }


    // ======== 另外一个思路 ======== //
    
    private static void mergeSortUp2Down(int[] a, int start, int end) {
        System.out.println("start = " + start + ", end = " + end);
        if (null == a || start >= end) {
            return;
        }
        int mid = (start + end) / 2;

        mergeSortUp2Down(a, start, mid);
        mergeSortUp2Down(a, mid + 1, end);
        merge(a, start, mid, end);
    }

    private static void merge(int[]a, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        // 第1个有序集合的起始下标
        int firstIndex = start;
        // 第2个有序集合的起始下标
        int secondIndex = mid + 1;
        // 临时数组的下标
        int tempIndex = 0;

        while (firstIndex <= mid && secondIndex <= end) {
            if (a[firstIndex] <= a[secondIndex]) {
                temp[tempIndex++] = a[firstIndex++];
            }
            else {
                temp[tempIndex++] = a[secondIndex++];
            }
        }

        while (firstIndex <= mid) {
            temp[tempIndex++] = a[firstIndex++];
        }

        while (secondIndex <= end) {
            temp[tempIndex++] = a[secondIndex++];
        }

        // 将排序后的元素，全部整合到数组a
        for (int i = 0; i < tempIndex; i++) {
            a[start+i] = temp[i];
        }

        temp = null;
    }
}
